package com.cat.dynamicPlanning;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-cost-path-with-alternating-directions-ii/description/
 * @create 2025/8/31 15:59
 * @since JDK17
 */

public class Solution36 {
    int[][] cost;
    int m, n;
    long [][]dp;
    long f(int x, int y, int cur) {
        if (x == m && y == n) {
            return m * n;
        }
        if (dp[x][y] != -1) {
            return dp[x][y];
        }
        long ans = Long.MIN_VALUE, p1 = Long.MAX_VALUE / 2, p2 = Long.MAX_VALUE / 2;
        if (cur % 2 == 0) {
            ans = cost[x][y] + f(x, y, cur + 1);
        } else {
            if (x + 1 < m) {
                p1 = f(x + 1, y, cur + 1);
            }
            if (y + 1 < n) {
                p2 = f(x, y + 1, cur + 1);
            }
        }
        return dp[x][y] = Math.min(ans, (x + 1) * (y + 1) + Math.min(p1, p2));
    }
    public long minCost(int m, int n, int[][] waitCost) {
        dp = new long[m][n];
        cost = waitCost;
        this.m = m;
        this.n = n;
        for (int i = 0; i < m; i++) {
            Arrays.fill(dp[i], -1);
        }
        f(0, 0, 1);
        return dp[m - 1][n - 1];
    }
}
